import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

public class QuickSortLomuto {
    public static void sort(int[] arr){
        quick(arr, 0, arr.length - 1);
    }
    private static void quick(int[] arr, int left, int right){
        if (left >= right){
            return;
        }
        int pv = partition2(arr, left, right);  // p代表基准点元素索引
        quick(arr, left, pv - 1);
        quick(arr, pv + 1, right);
    }

    private static int partition(int[] arr, int left, int right) {  //单边快排
        //随机元素作为基准点
        int radom = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
        swap(arr, radom, right);
        // 基准点元素值
        int pv = arr[right];
        int i = left;
        int j = left;
        while (j < right){
            if (arr[j] < pv){ // j 找到比基准点小的了, 没找到大的
                if (i != j){
                    swap(arr, i, j);
                }
                i++;
            }
            j++;
        }
        swap(arr, i, right);
        return i;
    }

    private static int partition1(int[] arr, int left, int right) { //双边快排
        //随机元素作为基准点
        int radom = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
        swap(arr, radom, left);
        int pv = arr[left];
        int i = left;
        int j = right;
        while (i < j){
            while (i < j && arr[j] > pv){
                j--;
            }
            while (i < j && arr[i] <= pv){
                i++;
            }
            swap(arr, i , j);
        }
        swap(arr, left, i);
        return i;
    }

    //处理重复值
    /*
        循环内
            i 从 left + 1 开始，从左向右找大的或相等的
            j 从 right 开始，从右向左找小的或相等的
            交换，i++ j--

        循环外 j 和 基准点交换，j 即为分区位置
     */
    private static int partition2(int[] a, int left, int right){
        int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
        swap(a, left, idx);
        int pv = a[left];
        int i = left + 1;
        int j = right;
        while (i <= j){
            // i 从左向右找大的或者相等的
            while (i <= j && a[i] < pv){
                i++;
            }
            while (i <= j && a[j] > pv){
                j--;
            }
            if (i <= j) {
                swap(a, i, j);
                i++;
                j--;
            }
        }
        swap(a, j, left);
        return j;
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void main(String[] args) {
        int[] a = {5, 3, 7, 2, 9, 8, 1, 4};
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}
